A field programmable gate array (FPGA) includes a plurality of configurable logic blocks (CLBs) and a configurable interconnect structure for connecting the CLBs to one another and otherwise routing signals through the FPGA. The overall structure of an FPGA is described by Freeman in U.S. Pat. No. Re. 34,363, incorporated herein by reference. The tristate bus and carry logic structure of a FPGA are typically orthogonal to one another. Specifically, dedicated tristate buses run in a horizontal direction along the bit slices of an FPGA as described, for instance, in U.S. Pat. No. 5,677,638, incorporated herein by reference, while dedicated carry logic runs in a vertical direction across the bit slices of an FPGA as described, for instance, in U.S. Pat. No. 5,629,886, incorporated herein by reference.
An FPGA 10 of the type described in U.S. Pat. No. 5,677,638 having an emulated tristate bus structure formed in the horizontal direction along bit slices is shown in FIG. 1. The FPGA 10 includes a plurality of logic units 11 each having a CLB 12, a multiplexer 13, a data line I, and an enable line E. The CLBs 12, each of which may, for instance, be configured to add two 4-bit numbers to produce a 4-bit sum and a 1-bit carry signal, communicate with one another and other components (not shown) of the FPGA 10 using an interconnect structure 14. The multiplexers 13 of adjacent logic units 11 are cascaded together to form a chain across corresponding logic units 11, where the second input and control terminals of the multiplexers 13 are connected to associated input data and input enable lines I and E, respectively. The output of the final multiplexer in the chain can be routed back to any bit slice requiring the tristate output value as an input.
Data signals are provided on respective input lines I1-I8 and corresponding enable signals are provided on respective enable lines E1-E8. If none of the enable signals on lines E1-E4 are asserted, then the output signal from multiplexer 15a is forwarded through multiplexer chain 13a-13d and buffer 19a to line 17b. If, on the other hand, an enable signal on one of lines E1-E4 is asserted, then the input signal on the corresponding multiplexer input line I appears on bus line 17b. In this manner, the multiplexer chain 13a-13d forms a tristate bus across logic units 11a-11d, thereby allowing one of the input signals on respective lines I1-I4 to drive the bus line 17b. The multiplexer chain 13e-13h forms a tristate bus across logic units 11e-11h in a similar manner.
Adjacent multiplexer chains are selectively coupled together using contacts 14 and multiplexers 15 to form longer multiplexer chains. Predetermined values stored in memories 16 control respective multiplexers 15.For instance, when the value stored in memory 16a is "0", multiplexer 15a couples the signal on line 17a to the first input terminal of the multiplexer 13a, thereby connecting the chain of multiplexers 13a-13d to the multiplexer chain to the left (not shown). On the other hand, when the value in memory 16a is "1", multiplexer 15a couples the signal on line 18a to the multiplexer 13a, thereby sourcing a signal from either the interconnect structure or ground potential. Thus, if the value stored in memory 16b is a logic "0" and if the contact 14b is not electrically coupled to the interconnect structure 14, then multiplexers 13a-13h form a common, 8-input tristate bus across logic units 11a-11h.
A carry logic circuit 20 employed within a CLB of the type described in U.S. Pat. No. 5,629,886 is shown in FIG. 2. The carry logic circuit 20 includes one bit of a carry chain that runs in the vertical direction to propagate carry signals across bit slices of input signals A and B. Note that the sum information, which travels horizontally from input lines A.sub.i, B.sub.i to sum line S.sub.i, runs orthogonal to the carry information, which travels vertically from input line C.sub.i to the output line C.sub.i+1.
The dedicated bus structure, carry logic, and sum logic of conventional FPGA structures are well suited for performing a number of programmable functions, including addition and subtraction, where the carry information runs orthogonal to the sum information. However, when implementing more complicated functions such as, for instance, a carry-save multiplier, the above-described structure is restrictive. For instance, where it is desired to multiply two 8-bit numbers X[7:0]*Y[7:0], the first number X[7:0] is logically ANDed with each bit of the second number Y[n] to produce eight 8-bit partial products. These partial products, which may be temporarily stored in an array 30, as depicted in FIG. 3, are then combined to form a 16-bit sum of products Z[15:0], i.e., X[7:0]*Y[7:0]=Z[15:0]. When combining the partial products using the well-known carry-save technique to reduce delay, sum information travels diagonally through the array 30, as indicated in FIG. 3 by the SUM arrow. Carry information propagates horizontally through each of the 8 rows of the array 30, as indicated in FIG. 3 by the horizontal CARRY arrows. The sum information is combined with the eight row carry bits in a single adder, as modeled by the rightmost column of the array 30, whereby the final carry bits propagate in the vertical direction through the array 30, as indicated by the single vertical CARRY arrow in FIG. 3. Accordingly, since carry information travels in both the vertical and horizontal directions in a carry-save multiplier circuit, it is desirable to provide an FPGA having carry paths in such orthogonal directions. Further, since silicon area is expensive, it would be desirable for such a structure to require minimal circuit components.